#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;
namespace bit
{
// 为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身，
template<class T>
struct HashBucketNode
{
    T _data;
    HashBucketNode<T>* _pNext;

    HashBucketNode(const T& data)
        : _data(data), _pNext(nullptr)
    {}
};
template<class K>
struct DefHashF
{
    size_t operator()(const K& key) const
    {
        return std::hash<K>()(key);
    }
};
template <class K, class V, class KeyOfValue, class HF>
struct HBIterator; // 这里要做一个前置的声明处理
template<class K, class V, class KeyOfValue, class HF>
class HashBucket {
public:
    typedef HashBucketNode<V> Node;
    friend struct HBIterator<K, V, KeyOfValue, HF>;
    typedef struct HBIterator<K, V, KeyOfValue, HF> Iterator;
    HashBucket(size_t capacity = 100)
        :_size(0) {
            _ht.resize(capacity, nullptr);
        }
    ~HashBucket() {
        clear();
    }
    size_t BucketCount() const {
        return _ht.size();
    }
    size_t size() const {
        return _size;
    }
    bool empty() const {
        return _size == 0;
    }
    Iterator begin() {
        for(size_t i = 0; i < _ht.size(); i++) {
            if(_ht[i]) {
                return Iterator(_ht[i], this);
            }
        }
        return end();
    }
    Iterator end() {
        return Iterator(nullptr, this);
    }
    size_t HashFunc(const K& key) const {
        return HF()(key) % _ht.size();
    }
    void rehash() {
        size_t newSize = _ht.size() * 2;
        std::vector<Node*> newHT(newSize, nullptr);
        for(auto old : _ht) {
            while (old) {
                Node* next = old->_pNext;
                size_t pos = HF()(KeyOfValue()(old->_data)) % newSize;
                old->_pNext = newHT[pos];
                newHT[pos] = old;
                old = next;
            }
        }
        _ht.swap(newHT);
    }
    Iterator Find(const K& key) {
        size_t pos = HashFunc(key);
        Node* cur = _ht[pos];
        while (cur) {
            if(KeyOfValue()(cur->_data) == key) {
                return Iterator(cur, this);
            }
            cur = cur->_pNext;
        }
        return end();
    }
    size_t Count(const K& key) {
        Iterator it = Find(key);
        return it == end() ? 0 : 1;
    }
    std::pair<Iterator, bool> InsertUnique(const V& data) {
        K key = KeyOfValue()(data);
        size_t pos = HashFunc(key);
        Node* cur = _ht[pos];
        // 有值就返回了
        while (cur) {
            if(KeyOfValue()(cur->_data) == key) {
                return { Iterator(cur, this), false};
            }
            cur = cur->_pNext;
        }
        Node* newnode = new Node(data);
        newnode->_pNext = _ht[pos];
        _ht[pos] = newnode;
        _size++;
        // 负载因子过大，扩容，注意这里是开散列
        if(_size > _ht.size() * 2) {
            rehash();
        }
        return { Iterator(newnode, this), true };
    }
    std::pair<Iterator, bool> Insert(const V& data) {
        return InsertUnique(data);
    }
    Iterator Erase(Iterator pos) {
        if(pos._pNode == nullptr) {
            return end();
        }// 从这里开始一定是有值要删的
        Node* node = pos._pNode;
        K key = KeyOfValue()(node->_data);
        size_t index = HashFunc(key);
        Node*& head = _ht[index];
        if(head == node) { // 删除头节点
            head = node->_pNext;
            Node* next = node->_pNext;
            delete node;
            _size--;
            return Iterator(next, this);
        }
        Node* prev = head; // 删除中间节点
        while (prev->_pNext != node) {
            prev = prev->_pNext;
        }
        prev->_pNext = node->_pNext;
        Node* next = node->_pNext;
        delete node;
        _size--;
        return Iterator(next, this);
    }
    size_t BucketSize(const K& key) {
        size_t index = HashFunc(key);
        Node* cur = _ht[index];
        size_t count = 0;
        while (cur) {
            cur = cur->_pNext;
            count++;
        }
        return count;
    }
    void clear() {
        for(auto& h : _ht) {
            while (h) {
                Node* next = h->_pNext;
                delete h;
                h = next;
            }
            h = nullptr;
        }
        _size = 0;
    }
private:
    vector<Node*> _ht;
    size_t _size;
};

// 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作
template <class K, class V, class KeyOfValue, class HF>
struct HBIterator 
{
	typedef HashBucket<K, V, KeyOfValue, HF> HashBucket;
	typedef HashBucketNode<V>* PNode;
	typedef HBIterator<K, V, KeyOfValue, HF> Self;

	HBIterator(PNode pNode = nullptr, HashBucket* pHt = nullptr)
    :_pNode(pNode), _pHt(pHt) {}
	Self& operator++()
	{
        if(_pNode == nullptr) {
            return *this;
        }
         // 当前迭代器所指节点后还有节点时直接取其下一个节点
		if (_pNode->_pNext)
			_pNode = _pNode->_pNext;
		else
		{
			// 找下一个不空的桶，返回该桶中第一个节点
			size_t bucketNo = _pHt->HashFunc(KeyOfValue()(_pNode->_data))+1;
			for (; bucketNo < _pHt->BucketCount(); ++bucketNo)
			{
				if (_pHt->_ht[bucketNo]) {
                    _pNode = _pHt->_ht[bucketNo];
                    return *this;
                }
			}
		}
        _pNode = nullptr;
		return *this;
	}
	Self operator++(int) {
        Self temp(*this);
        ++(*this);
        return temp;
    }
    V& operator*() {
        return _pNode->_data;
    }
	V* operator->() {
        return &_pNode->_data;
    }
	bool operator==(const Self& it) const {
        return _pNode == it._pNode;
    }
	bool operator!=(const Self& it) const {
        return _pNode != it._pNode;
    }
	PNode _pNode;             // 当前迭代器关联的节点
	HashBucket* _pHt;         // 哈希桶--主要是为了找下一个空桶时候方便
};

// unordered_map中存储的是pair<K, V>的键值对，K为key的类型，V为value的类型，HF哈希函数类型
// unordered_map在实现时，只需将hashbucket中的接口重新封装即可
template<class K, class V, class HF = DefHashF<K>>
class unordered_map
{
    
    // 通过key获取value的操作
	struct KeyOfValue
	{
		const K& operator()(const pair<K, V>& data)
		{ return data.first;}
	};
    typedef HashBucket<K, pair<K, V>, KeyOfValue, HF> HT;
public:
	typedef typename HT::Iterator iterator;
public:
	unordered_map(): _ht()
	{}
	////////////////////////////////////////////////////
	iterator begin(){ return _ht.begin();}
	iterator end(){ return _ht.end();}
	////////////////////////////////////////////////////////////
	// capacity
	size_t size()const{ return _ht.size();}
	bool empty()const{return _ht.empty();}
	///////////////////////////////////////////////////////////
	// Acess
	V& operator[](const K& key) // 实际等价于 hash.operator[](key)
	{
		pair<iterator, bool> ret = _ht.InsertUnique(pair<K, V>(key, V()));
        return ret.first->second;
	}
	const V& operator[](const K& key)const;
	//////////////////////////////////////////////////////////
	// lookup
	iterator find(const K& key){ return _ht.Find(key);}
	size_t count(const K& key){ return _ht.Count(key);}
	/////////////////////////////////////////////////
	// modify
	pair<iterator, bool> insert(const pair<K, V>& valye)
	{ return _ht.Insert(valye);}

	iterator erase(iterator position)
	{ return _ht.Erase(position);}
    ////////////////////////////////////////////////////////////
	// bucket
	size_t bucket_count(){ return _ht.BucketCount();}
	size_t bucket_size(const K& key){ return _ht.BucketSize(key);}
private:
	HT _ht;
};
}

using namespace std;
using namespace bit;

int main()
{
    unordered_map<int, string, DefHashF<int>> mp;

    cout << "===== Insert 测试 =====" << endl;
    mp.insert({1, "one"});
    mp.insert({2, "two"});
    mp.insert({3, "three"});

    // 插入重复 key
    auto ret = mp.insert({2, "TWO"});
    cout << "插入重复 key 2 是否成功: " << (ret.second ? "是" : "否") << endl;

    cout << "\n===== operator[] 测试 =====" << endl;
    mp[4] = "four";            // 自动插入
    cout << "mp[4] = " << mp[4] << endl;

    mp[2] = "modified-two";    // 修改
    cout << "修改后的 mp[2] = " << mp[2] << endl;

    cout << "\n===== find 测试 =====" << endl;
    auto it = mp.find(3);
    if (it != mp.end())
        cout << "找到 key=3, value=" << it->second << endl;

    cout << "\n===== 遍历测试 =====" << endl;
    for (auto& kv : mp)
    {
        cout << kv.first << " : " << kv.second << endl;
    }

    cout << "\n===== bucket 信息 =====" << endl;
    cout << "bucket_count = " << mp.bucket_count() << endl;
    cout << "bucket_size(1) = " << mp.bucket_size(1) << endl;

    cout << "\n===== erase 删除测试 =====" << endl;
    auto it2 = mp.find(2);
    if (it2 != mp.end())
    {
        mp.erase(it2);
        cout << "删除 key=2 完成" << endl;
    }

    cout << "当前所有元素：" << endl;
    for (auto& kv : mp)
    {
        cout << kv.first << " : " << kv.second << endl;
    }

    cout << "\n===== count 测试 =====" << endl;
    cout << "count(2) = " << mp.count(2) << endl;
    cout << "count(3) = " << mp.count(3) << endl;

    return 0;
}
